/*
Copyright (c) 2008, Mike Gashler

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/

#ifndef __GQUEUE_H__
#define __GQUEUE_H__

#include <string.h>
#include "app.h"

// A helper class used by GQueue
class GQueueChunk
{
public:
	GQueueChunk* m_pNext;
	int m_nSize;
	unsigned char* m_pData;
	bool m_bDelete;

	GQueueChunk(int nSize, const unsigned char* pStaticData);
	~GQueueChunk();
};


// A FIFO queue for arbitrary data
class GQueue
{
protected:
	int m_nDefaultChunkSize;
	int m_nInPos;
	int m_nOutPos;
	int m_nDataSize;
	GQueueChunk* m_pFirstChunk;
	GQueueChunk* m_pLastChunk;
	GQueueChunk* m_pExtra;
	GQueueChunk* m_pExtraStatic;

public:
	GQueue(int nChunkSize = 2048);
	~GQueue();

	void Flush();

	// This method takes ownership of pBuf (instead of
	// copying it like "Push" does.
	void PushStatic(const unsigned char* pBuf, int nBufSize);

	inline void Push(const unsigned char* pData, int nSize)
	{
		GQueueChunk* pCurrentChunk = m_pLastChunk;
		if(!pCurrentChunk || pCurrentChunk->m_nSize - m_nInPos < nSize)
			pCurrentChunk = MakeNewChunk(nSize);
		memcpy(&pCurrentChunk->m_pData[m_nInPos], pData, nSize);
		m_nInPos += nSize;
		m_nDataSize += nSize;
	}

	inline void Push(const wchar_t wc) { Push((const unsigned char*)&wc, sizeof(wchar_t)); }
	inline void Push(const char c) { Push((const unsigned char*)&c, sizeof(char)); }
	inline void Push(const int n) { Push((const unsigned char*)&n, sizeof(int)); }
	inline void Push(const void* pointer) { Push((const unsigned char*)&pointer, sizeof(void*)); }
	inline void Push(const unsigned int n) { Push((const unsigned char*)&n, sizeof(unsigned int)); }
	inline void Push(const unsigned char uc) { Push((const unsigned char*)&uc, sizeof(unsigned char)); }
	inline void Push(const float f) { Push((const unsigned char*)&f, sizeof(float)); }
	inline void Push(const double d) { Push((const unsigned char*)&d, sizeof(double)); }
	inline void Push(const char* szString) { if(szString) Push((const unsigned char*)szString, (int)strlen(szString)); }
	inline void Push(const wchar_t* wszString, int nLen) { Push((const unsigned char*)wszString, sizeof(wchar_t) * nLen); }

	bool Pop(unsigned char* pData, int nSize)
	{
		int nPart;
		while(true)
		{
			if(!m_pFirstChunk)
				return false;
			nPart = MIN(nSize, m_pFirstChunk->m_nSize - m_nOutPos);
			memcpy(pData, &m_pFirstChunk->m_pData[m_nOutPos], nPart);
			m_nDataSize -= nPart;
			m_nOutPos += nPart;
			nSize -= nPart;
			if(nSize <= 0)
				return true;
			pData += nPart;
			DropFirstChunk();
		}
	}

	inline bool Pop(wchar_t* pwc) { return Pop((unsigned char*)pwc, sizeof(wchar_t)); }
	inline bool Pop(char* pc) { return Pop((unsigned char*)pc, sizeof(char)); }
	inline bool Pop(int* pn) { return Pop((unsigned char*)pn, sizeof(int)); }
	inline bool Pop(void** pointer) { return Pop((unsigned char*)pointer, sizeof(void*)); }
	inline bool Pop(unsigned int* pui) { return Pop((unsigned char*)pui, sizeof(unsigned int)); }
	inline bool Pop(unsigned char* puc) { return Pop(puc, sizeof(unsigned char)); }
	inline bool Pop(float* pf) { return Pop((unsigned char*)pf, sizeof(float)); }
	inline bool Pop(double* pd) { return Pop((unsigned char*)pd, sizeof(double)); }

	int GetSize() { return m_nDataSize; }
	char* DumpToString(); // note: you must delete the string this returns

	// This puts data into an arbitrary position in the queue. It inserts
	// '\0' as padding if necessary, and it overwrites any data already
	// existing at that location. Behavior is undefined if you poke data
	// past the end of the queue.
	void Poke(int nIndex, const unsigned char* pBuf, int nLen);

protected:
	void Link(GQueueChunk* pChunk);
	GQueueChunk* UnlinkFirst();
	GQueueChunk* MakeNewChunk(int nMinSize);
	void DropFirstChunk();
};




class GPointerQueueChunk
{
public:
	GPointerQueueChunk* m_pNext;
	void** m_pData;

	GPointerQueueChunk(int nChunkSize);
	~GPointerQueueChunk();
};

// A FIFO queue for pointers
class GPointerQueue
{
protected:
	int m_nChunkSize;
	int m_nInPos;
	int m_nOutPos;
	int m_nDataSize;
	GPointerQueueChunk* m_pFirstChunk;
	GPointerQueueChunk* m_pLastChunk;
	GPointerQueueChunk* m_pExtra;

public:
	GPointerQueue(int nChunkSize = 1024);
	virtual ~GPointerQueue();

	void Flush();

	// Add a pointer to the queue
	inline void Push(void* pointer)
	{
		if(m_nInPos >= m_nChunkSize)
			GetNewChunk();
		m_pLastChunk->m_pData[m_nInPos++] = pointer;
		m_nDataSize++;
	}

	// Read the next pointer from the queue
	inline void* Pop()
	{
		void* pPointer = m_pFirstChunk->m_pData[m_nOutPos++];
		m_nDataSize--;
		if(m_nOutPos >= m_nChunkSize)
			ThrowOutChunk();
		return pPointer;
	}

	// Peek at the pointer at the specified index. (index zero refers to the next pointer in line to be popped.)
	inline void* Peek(int index)
	{
		int start = m_nOutPos;
		int size = m_nDataSize;
		GPointerQueueChunk* pChunk = m_pFirstChunk;
		while(index >= m_nChunkSize - start)
		{
			if(!pChunk)
				ThrowError("index out of range");
			size -= (m_nChunkSize - start);
			index -= (m_nChunkSize - start);
			start = 0;
			pChunk = pChunk->m_pNext;
		}
		if(index >= size)
			ThrowError("index out of range");
		return pChunk->m_pData[start + index];
	}

	// Returns how many pointers are in the queue
	inline int GetSize() { return m_nDataSize; }

protected:
	void GetNewChunk();
	void ThrowOutChunk();
	void Link(GPointerQueueChunk* pChunk);
	GPointerQueueChunk* UnlinkFirst();
};




// A FIFO queue for integers
class GIntQueue
{
protected:
	int m_nChunkSize;
	int m_nInPos;
	int m_nOutPos;
	int m_nDataSize;
	GPointerQueueChunk* m_pFirstChunk;
	GPointerQueueChunk* m_pLastChunk;
	GPointerQueueChunk* m_pExtra;

public:
	GIntQueue(int nChunkSize = 1024);
	virtual ~GIntQueue();

	void Flush();

	// Add an int to the queue
	inline void Push(int i)
	{
		if(m_nInPos >= m_nChunkSize)
			GetNewChunk();
		((int*)m_pLastChunk->m_pData)[m_nInPos++] = i;
		m_nDataSize++;
	}

	// Read the next int from the queue
	inline int Pop()
	{
		int i = ((int*)m_pFirstChunk->m_pData)[m_nOutPos++];
		m_nDataSize--;
		if(m_nOutPos >= m_nChunkSize)
			ThrowOutChunk();
		return i;
	}

	// Peek at the next int, but don't actually pop it
	inline int Peek()
	{
		return ((int*)m_pFirstChunk->m_pData)[m_nOutPos];
	}

	// Returns how many ints are in the queue
	inline int GetSize() { return m_nDataSize; }

protected:
	void GetNewChunk();
	void ThrowOutChunk();
	void Link(GPointerQueueChunk* pChunk);
	GPointerQueueChunk* UnlinkFirst();
};

#endif // __GQUEUE_H__
